<!doctype html>



  


<html class="theme-next mist use-motion">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>



<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />












  <link href="/vendors/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css"/>




  <link href="//fonts.googleapis.com/css?family=Lato:300,400,700,400italic&subset=latin,latin-ext" rel="stylesheet" type="text/css">



<link href="/vendors/font-awesome/css/font-awesome.min.css?v=4.4.0" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=0.5.0" rel="stylesheet" type="text/css" />


  <meta name="keywords" content="图,树,倍增思想," />








  <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico?v=0.5.0" />






<meta name="description" content="LCA在线算法 LCA: 求树上两个点最近公共祖先的算法
原理在讲解之前,我们先想两个问题,这两个问题也是LCA在线算法的核心:

问题1:如上图左部,f点有一个超能力–超能爬树:可以快速查看或爬到$2^j$远的结点上,例如爬到$2^0$远的结点就是1,$2^2$远的结点是b,每一次f到达某个点都可以知道是比要到的点高了还是低了.那如何结点f如何快速的到达点c? 结点f如何快速的到达它上面的任意点">
<meta property="og:type" content="article">
<meta property="og:title" content="LCA在线算法">
<meta property="og:url" content="http://yoursite.com/2016/03/LCA在线算法/index.html">
<meta property="og:site_name" content="Rainboy">
<meta property="og:description" content="LCA在线算法 LCA: 求树上两个点最近公共祖先的算法
原理在讲解之前,我们先想两个问题,这两个问题也是LCA在线算法的核心:

问题1:如上图左部,f点有一个超能力–超能爬树:可以快速查看或爬到$2^j$远的结点上,例如爬到$2^0$远的结点就是1,$2^2$远的结点是b,每一次f到达某个点都可以知道是比要到的点高了还是低了.那如何结点f如何快速的到达点c? 结点f如何快速的到达它上面的任意点">
<meta property="og:image" content="http://yoursite.com/images/LCA1.png">
<meta property="og:image" content="http://yoursite.com/images/LCA2.png">
<meta property="og:updated_time" content="2016-03-22T15:52:11.971Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="LCA在线算法">
<meta name="twitter:description" content="LCA在线算法 LCA: 求树上两个点最近公共祖先的算法
原理在讲解之前,我们先想两个问题,这两个问题也是LCA在线算法的核心:

问题1:如上图左部,f点有一个超能力–超能爬树:可以快速查看或爬到$2^j$远的结点上,例如爬到$2^0$远的结点就是1,$2^2$远的结点是b,每一次f到达某个点都可以知道是比要到的点高了还是低了.那如何结点f如何快速的到达点c? 结点f如何快速的到达它上面的任意点">
<meta name="twitter:image" content="http://yoursite.com/images/LCA1.png">



<script type="text/javascript" id="hexo.configuration">
  var NexT = window.NexT || {};
  var CONFIG = {
    scheme: 'Mist',
    sidebar: {"position":"left","display":"hide"},
    fancybox: true,
    motion: true,
    duoshuo: {
      userId: 0,
      author: 'Author'
    }
  };
</script>

  <title> LCA在线算法 | Rainboy </title>
</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh_Hans">

  










  
  
    
  

  <div class="container one-collumn sidebar-position-left page-post-detail ">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-meta ">
  

  <div class="custom-logo-site-title">
    <a href="/"  class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <span class="site-title">Rainboy</span>
      <span class="logo-line-after"><i></i></span>
    </a>
  </div>
  <p class="site-subtitle"></p>
</div>

<div class="site-nav-toggle">
  <button>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
  </button>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-home fa-fw"></i> <br />
            
            Startseite
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories" rel="section">
            
              <i class="menu-item-icon fa fa-th fa-fw"></i> <br />
            
            Kategorien
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives" rel="section">
            
              <i class="menu-item-icon fa fa-archive fa-fw"></i> <br />
            
            Archiv
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags" rel="section">
            
              <i class="menu-item-icon fa fa-tags fa-fw"></i> <br />
            
            Tags
          </a>
        </li>
      

      
    </ul>
  

  
</nav>

 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  
  

  
  
  

  <article class="post post-type-normal " itemscope itemtype="http://schema.org/Article">

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
            
            
              
                LCA在线算法
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">
            <span class="post-meta-item-icon">
              <i class="fa fa-calendar-o"></i>
            </span>
            <span class="post-meta-item-text">Veröffentlicht am</span>
            <time itemprop="dateCreated" datetime="2016-03-22T00:23:18+08:00" content="2016-03-22">
              2016-03-22
            </time>
          </span>

          
            <span class="post-category" >
              &nbsp; | &nbsp;
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              <span class="post-meta-item-text">in</span>
              
                <span itemprop="about" itemscope itemtype="https://schema.org/Thing">
                  <a href="/categories/算法/" itemprop="url" rel="index">
                    <span itemprop="name">算法</span>
                  </a>
                </span>

                
                

              
            </span>
          

          
            
              <span class="post-comments-count">
                &nbsp; | &nbsp;
                <a href="/2016/03/LCA在线算法/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count ds-thread-count" data-thread-key="2016/03/LCA在线算法/" itemprop="commentsCount"></span>
                </a>
              </span>
            
          

          

          
          

        </div>
      </header>
    


    <div class="post-body" itemprop="articleBody">

      
      

      
        <h1 id="LCA在线算法"><a href="#LCA在线算法" class="headerlink" title="LCA在线算法"></a>LCA在线算法</h1><p> LCA: 求树上两个点最近公共祖先的算法</p>
<h2 id="原理"><a href="#原理" class="headerlink" title="原理"></a>原理</h2><p>在讲解之前,我们先想两个问题,这两个问题也是LCA在线算法的核心:</p>
<p><img src="/images/LCA1.png" alt="LCA1"></p>
<h3 id="问题1"><a href="#问题1" class="headerlink" title="问题1:"></a>问题1:</h3><p>如上图左部,f点有一个<code>超能力</code>–超能爬树:可以快速查看或爬到$2^j$远的结点上,例如爬到$2^0$远的结点就是1,$2^2$远的结点是b,每一次f到达某个点都可以知道是比要到的点高了还是低了.<strong>那如何结点f如何快速的到达点c</strong>? <strong>结点f如何快速的到达它上面的任意点?</strong></p>
<p>想一想:折半查找应该算是最快的查找方法之一,$Nlog(n)$的时间复杂度.</p>
<p>那我们按下面的方法来找:</p>
<p>如上图左部的步骤:</p>
<ul>
<li>f先到最远的点,距离$2^2$远的点,也就是b看看,发现高了</li>
<li>因为了高了,那f到距离$2^1$远的点(d)看看,发现在低了</li>
<li>因为低了,说明要到达的点c在点d的上面,那f就爬到点d</li>
<li>f到距离$2^0$远的点c看看,发现就是这个点,f爬到这个.算法结束.</li>
</ul>
<p>更抽象的步骤:</p>
<ul>
<li>f先达到最高的地方,假如是$2^k$远的点</li>
<li>如果高了,那要找的点在下面,到$2^(k-1)$点,也就是到达最远的地方的一半远看看</li>
<li>如果低了,那说明要找的点在上面,那就先爬到个点,然后到达$2^(k-1)$远的地方看看</li>
<li>现在f已经到达了某个点,那f接着到现在位置的$2^(k-2)$远的地方看看</li>
<li>如果高了,那说明要找的点在下面(想一想这个时候要找的点在哪个区间),那到现在$2^(k-3)$远的地方看看</li>
<li>如果低了,那说明要找的点在上面,那就先爬到这个点,然后到达$2^(k-3)$的地方看看</li>
<li>经过上面的不停重复,那最后$k=0$,这个时候停下的位置就是f想要到达的点</li>
</ul>
<h3 id="问题2"><a href="#问题2" class="headerlink" title="问题2"></a>问题2</h3><p>看上图右部,f依然有它的<code>超能爬树</code>这个能力,现在最上面的点a,b,c是有色的点,f不能到达有色的点,但是它想到<br>离有色剖分最近的点怎么做?</p>
<p>如上图右部的步骤:</p>
<ul>
<li>f先到最远的点,距离$2^2$远的点,也就是b看看,发现是有色,不能到</li>
<li>那f到距离$2^1$远的点,也就是d看看,发现无色</li>
<li>因为d是无色,那f就爬到点d,但是d上面还有可能有无色的点(想一想哪个范围是),f爬到点d</li>
<li>f到距离$2^0$远的点c看看,发现是有色,不能到达,算法停止.f最后停下的地方就是最接近有色区域的点.</li>
</ul>
<p>更抽象的步骤:</p>
<p>通过<code>问题1</code>,点f可以通过不停减少k的方式,快速到达想要到达的点,且最后$k=0$,你把有色区域想成一个点,按这<br>种方式,f最后一点会到达这个点,但是你加上了一个限制条件: <strong>有色区域不能到达!</strong>.f的行为是尽可能的去,那最后f停下的<br>位置就是最近的位置</p>
<h3 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h3><p>上面的方法用一句话来形容:<strong>折半尝试</strong>,它会把结果的可能性每次缩小一半,最后$k=0$的时候只有两种可能性,要么是<br>自己,要么是上面一个点,所以可以得到答案.这是一中<code>倍增思想</code>.</p>
<h2 id="转为代码"><a href="#转为代码" class="headerlink" title="转为代码"></a>转为代码</h2><p><img src="/images/LCA2.png" alt="LCA2"></p>
<p>看这个图,我们分为这几个步骤来做</p>
<ul>
<li>初始化,也是ST部分,求任意点i的$2^j$倍祖先:$p[i,j]$</li>
<li>把点<code>9</code>和点<code>12</code>移到同一层,也就是找<code>12</code>和<code>9</code>同一层的祖先,得用是<strong>问题</strong>的方法</li>
<li>上面我们已经知道<code>LCA(9,12) == LCA(9,10)</code>,</li>
<li>点1,3都是祖先,但是不知道哪个点是最近公共祖先,所心只要我们近可能的接近<code>祖先区域</code>,那最近停下时候的点的父亲,就是所求.</li>
</ul>
<h3 id="ST-预处理"><a href="#ST-预处理" class="headerlink" title="ST 预处理"></a>ST 预处理</h3><p> 已知:点i的父亲是f[i],深度是d[i],<code>p[i][j]</code>表示点i的$2^j$倍祖先,那么根据DP思想,我们得到一个重要的公式:</p>
<p>$$p[i,j]=\left\{\begin{matrix} &amp; father[i] &amp;j=0 \\ &amp; p[p[i,j-1],j-1] &amp;j&gt;0\end{matrix}\right.$$</p>
<p>那么ST代码:</p>
<pre><code>int d[100] = {0};//每个点的深度
int f[100];//每个点的父亲
int p[100][100];

void st(){
    int i,j;
    memset(p,-1,sizeof(p));//想一想:为什么是-1
    for(i=1;i&lt;=n;i++) // n个点,dp边界
        p[i,0]=f[i];

    //n个点,理论最深是n,也就是最大有n-1倍祖先,我们算大一点:算成n倍祖先
    // 2^j =n ---&gt;j=log(n)/log(2)
    for(j=1;j&lt;=(int)(log(n)/log(2));j++) 
        for(i=1;i&lt;=n;i++)
            if(p[i][j-1] != -1)// [1] p[i][j-1] != -1 表明可以用自己去更新别人,为什么要有这个判断?
                p[i,j] = p[p[i,j-1],j-1];
}
</code></pre><h3 id="两个点到同一层"><a href="#两个点到同一层" class="headerlink" title="两个点到同一层"></a>两个点到同一层</h3><pre><code>/*    先判断是否 d[a] &gt; d[b] ，如果是的话就交换一下(保证 a 的深度小于b，方便下面的操作) */
int i;
if(d[a] &gt; d[b])
{
    int tmp =a;
    a=b;
    b=tmp;
}

/* 转为找同层结点  d[a] &lt;= d[b] */
/* 这种找法 能成功的原因,看折半查找原理*/

int k = (int)(log(d[b]-1)/log(2));//公式 root 点是b点d[b]-1倍祖先
for(i=k;i&gt;=0;i--){
    if(d[b]-(1&lt;&lt;i) &gt;=d[a]) //1&lt;&lt;i ==2^i,&gt;=d[a] 没有a的高,还要往上爬
        b=p[b][i];
}
if(a == b)    //这种情况:b是a的子树
    return a;
</code></pre><h3 id="同一深度的点一起向上爬"><a href="#同一深度的点一起向上爬" class="headerlink" title="同一深度的点一起向上爬"></a>同一深度的点一起向上爬</h3><pre><code>//爬树中,原理:拆半查找原理
k = (int)(log(d[b]-1)/log(2));

for(i=k;i&gt;=0;i--)
    if(p[a][i] != p[b][i])
    {
        a=p[a][i];
        b=p[b][i];
    }
return p[a][0];
</code></pre><h2 id="完整代码"><a href="#完整代码" class="headerlink" title="完整代码"></a>完整代码</h2><pre><code>/*
数据:
1
1 2 3 4
3 5 6 7
6 8 9
7 10 11
10 12 13
*/

#include &lt;cstdio&gt;
#include &lt;cstring&gt;
#include &lt;cmath&gt; //为了使用log()函数

int n; // 总共有n个点

int d[100] = {0};//每个点的深度
int f[100];//每个点的父亲
int p[100][100];

void st(){
    int i,j;
    memset(p,-1,sizeof(p));
    for(i=1;i&lt;=n;i++) // n个点,dp边界
        p[i][0]=f[i];

    //n个点,理论最深是n,也就是最大有n-1倍祖先,我们算大一点:算成n倍祖先
    // 2^j =n ---&gt;j=log(n)/log(2)
    for(j=1;j&lt;=(int)(log(n)/log(2));j++)
        for(i=1;i&lt;=n;i++)
            if(p[i][j-1] != -1)// [1] p[i][j-1] != -1 表明可以用自己去更新别人,为什么要有这个判断?
                p[i][j] = p[p[i][j-1]][j-1];
}

// 求点a,b的最近公共祖先
int LCA(int a,int b){
    /*    先判断是否 d[a] &gt; d[b] ，如果是的话就交换一下(保证 a 的深度小于b，方便下面的操作) */
    int i;
    if(d[a] &gt; d[b])
    {
        int tmp =a;
        a=b;
        b=tmp;
    }

    /* 转为找同层结点  d[a] &lt;= d[b] */
    /* 这种找法 能成功的原因,看折半查找原理*/

    int k = (int)(log(d[b]-1)/log(2));//公式 root 点是b点d[b]-1倍祖先
    for(i=k;i&gt;=0;i--){
        if(d[b]-(1&lt;&lt;i) &gt;=d[a])
            b=p[b][i];
    }
    if(a == b)    //这种情况:b是a的子树
        return a;

    //爬树中,原理:拆半查找原理
    k = (int)(log(d[b]-1)/log(2));

    for(i=k;i&gt;=0;i--)
        if(p[a][i] != p[b][i])
        {
            a=p[a][i];
            b=p[b][i];
        }

    return p[a][0];
}


int main(){
    //太难受了,手动建立树
    n=13;

    int root =1;
    d[root] =1;
    f[root] = -1;// [2]  在这里,f[root] =-1 比较好,可以少算很多
    f[3]=f[2]=f[4] =root;    d[3] = d[2]=d[4]=d[root]+1;
    f[5]=f[6]=f[7] =3;        d[5] = d[6] =d[7] =d[3]+1;
    f[10]=f[11] =7;            d[10]=d[11] =d[7]+1;
    f[12]=f[13]=10;            d[12]=d[13]=d[10]+1;
    f[8]=f[9]=6;                d[8]=d[9]=d[6]+1;


    //预处理
    st();
    //LCA
    int tmp = LCA(9,12);
    printf(&quot;%d&quot;,tmp);
    return 0;
}
</code></pre>
      
    </div>

    <div>
      
        
      
    </div>

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/图/" rel="tag">#图</a>
          
            <a href="/tags/树/" rel="tag">#树</a>
          
            <a href="/tags/倍增思想/" rel="tag">#倍增思想</a>
          
        </div>
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2016/03/STL-vector/" rel="next" title="STL 学习讲解一">
                <i class="fa fa-chevron-left"></i> STL 学习讲解一
              </a>
            
          </div>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2016/03/二进制优化原理/" rel="prev" title="二进制优化原理">
                二进制优化原理 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          
  <div class="comments" id="comments">
    
      <div class="ds-thread" data-thread-key="2016/03/LCA在线算法/"
           data-title="LCA在线算法" data-url="http://yoursite.com/2016/03/LCA在线算法/">
      </div>
    
  </div>


        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap" >
            Inhaltsverzeichnis
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview">
            Übersicht
          </li>
        </ul>
      

      <section class="site-overview sidebar-panel ">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
          <img class="site-author-image" itemprop="image"
               src="/images/avatar.jpg"
               alt="Rainboy" />
          <p class="site-author-name" itemprop="name">Rainboy</p>
          <p class="site-description motion-element" itemprop="description">Rainboy Personal Blog by Hexo</p>
        </div>
        <nav class="site-state motion-element">
          <div class="site-state-item site-state-posts">
            <a href="/archives">
              <span class="site-state-item-count">16</span>
              <span class="site-state-item-name">Artikel</span>
            </a>
          </div>

          
            <div class="site-state-item site-state-categories">
              <a href="/categories">
                <span class="site-state-item-count">10</span>
                <span class="site-state-item-name">Kategorien</span>
              </a>
            </div>
          

          
            <div class="site-state-item site-state-tags">
              <a href="/tags">
                <span class="site-state-item-count">23</span>
                <span class="site-state-item-name">Tags</span>
              </a>
            </div>
          

        </nav>

        

        <div class="links-of-author motion-element">
          
        </div>

        
        

        
        <div class="links-of-blogroll motion-element">
          
        </div>

      </section>

      
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc-indicator-top post-toc-indicator">
            <i class="fa fa-angle-double-up"></i>
          </div>
          <div class="post-toc">
            
              
            
            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#LCA在线算法"><span class="nav-number">1.</span> <span class="nav-text">LCA在线算法</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#原理"><span class="nav-number">1.1.</span> <span class="nav-text">原理</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#问题1"><span class="nav-number">1.1.1.</span> <span class="nav-text">问题1:</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#问题2"><span class="nav-number">1.1.2.</span> <span class="nav-text">问题2</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#总结"><span class="nav-number">1.1.3.</span> <span class="nav-text">总结</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#转为代码"><span class="nav-number">1.2.</span> <span class="nav-text">转为代码</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#ST-预处理"><span class="nav-number">1.2.1.</span> <span class="nav-text">ST 预处理</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#两个点到同一层"><span class="nav-number">1.2.2.</span> <span class="nav-text">两个点到同一层</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#同一深度的点一起向上爬"><span class="nav-number">1.2.3.</span> <span class="nav-text">同一深度的点一起向上爬</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#完整代码"><span class="nav-number">1.3.</span> <span class="nav-text">完整代码</span></a></li></ol></li></ol></div>
            
          </div>
          <div class="post-toc-indicator-bottom post-toc-indicator">
            <i class="fa fa-angle-double-down"></i>
          </div>
        </section>
      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright" >
  
  &copy; 
  <span itemprop="copyrightYear">2016</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Rainboy</span>
</div>

<div class="powered-by">
  Erstellt mit  <a class="theme-link" href="http://hexo.io">Hexo</a>
</div>

<div class="theme-info">
  Theme -
  <a class="theme-link" href="https://github.com/iissnan/hexo-theme-next">
    NexT.Mist
  </a>
</div>



      </div>
    </footer>

    <div class="back-to-top">
      <i class="fa fa-arrow-up"></i>
    </div>
  </div>

  


  




<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>


  <script type="text/javascript" src="/vendors/jquery/index.js?v=2.1.3"></script>

  <script type="text/javascript" src="/vendors/fastclick/lib/fastclick.min.js?v=1.0.6"></script>

  <script type="text/javascript" src="/vendors/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>

  <script type="text/javascript" src="/vendors/velocity/velocity.min.js"></script>

  <script type="text/javascript" src="/vendors/velocity/velocity.ui.min.js"></script>

  <script type="text/javascript" src="/vendors/fancybox/source/jquery.fancybox.pack.js"></script>


  


  <script type="text/javascript" src="/js/src/utils.js?v=0.5.0"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=0.5.0"></script>



  
  

  
  
<script type="text/javascript" src="/js/src/scrollspy.js?v=0.5.0"></script>

<script type="text/javascript" id="sidebar.toc.highlight">
  $(document).ready(function () {
    var tocSelector = '.post-toc';
    var $tocSelector = $(tocSelector);
    var activeCurrentSelector = '.active-current';

    $tocSelector
      .on('activate.bs.scrollspy', function () {
        var $currentActiveElement = $(tocSelector + ' .active').last();

        removeCurrentActiveClass();
        $currentActiveElement.addClass('active-current');

        $tocSelector[0].scrollTop = $currentActiveElement.position().top;
      })
      .on('clear.bs.scrollspy', function () {
        removeCurrentActiveClass();
      });

    function removeCurrentActiveClass () {
      $(tocSelector + ' ' + activeCurrentSelector)
        .removeClass(activeCurrentSelector.substring(1));
    }

    function processTOC () {
      getTOCMaxHeight();
      toggleTOCOverflowIndicators();
    }

    function getTOCMaxHeight () {
      var height = $('.sidebar').height() -
                   $tocSelector.position().top -
                   $('.post-toc-indicator-bottom').height();

      $tocSelector.css('height', height);

      return height;
    }

    function toggleTOCOverflowIndicators () {
      tocOverflowIndicator(
        '.post-toc-indicator-top',
        $tocSelector.scrollTop() > 0 ? 'show' : 'hide'
      );

      tocOverflowIndicator(
        '.post-toc-indicator-bottom',
        $tocSelector.scrollTop() >= $tocSelector.find('ol').height() - $tocSelector.height() ? 'hide' : 'show'
      )
    }

    $(document).on('sidebar.motion.complete', function () {
      processTOC();
    });

    $('body').scrollspy({ target: tocSelector });
    $(window).on('resize', function () {
      if ( $('.sidebar').hasClass('sidebar-active') ) {
        processTOC();
      }
    });

    onScroll($tocSelector);

    function onScroll (element) {
      element.on('mousewheel DOMMouseScroll', function (event) {
          var oe = event.originalEvent;
          var delta = oe.wheelDelta || -oe.detail;

          this.scrollTop += ( delta < 0 ? 1 : -1 ) * 30;
          event.preventDefault();

          toggleTOCOverflowIndicators();
      });
    }

    function tocOverflowIndicator (indicator, action) {
      var $indicator = $(indicator);
      var opacity = action === 'show' ? 1 : 0;
      $indicator.velocity ?
        $indicator.velocity('stop').velocity({
          opacity: opacity
        }, { duration: 100 }) :
        $indicator.stop().animate({
          opacity: opacity
        }, 100);
    }

  });
</script>

<script type="text/javascript" id="sidebar.nav">
  $(document).ready(function () {
    var html = $('html');
    var TAB_ANIMATE_DURATION = 200;
    var hasVelocity = $.isFunction(html.velocity);

    $('.sidebar-nav li').on('click', function () {
      var item = $(this);
      var activeTabClassName = 'sidebar-nav-active';
      var activePanelClassName = 'sidebar-panel-active';
      if (item.hasClass(activeTabClassName)) {
        return;
      }

      var currentTarget = $('.' + activePanelClassName);
      var target = $('.' + item.data('target'));

      hasVelocity ?
        currentTarget.velocity('transition.slideUpOut', TAB_ANIMATE_DURATION, function () {
          target
            .velocity('stop')
            .velocity('transition.slideDownIn', TAB_ANIMATE_DURATION)
            .addClass(activePanelClassName);
        }) :
        currentTarget.animate({ opacity: 0 }, TAB_ANIMATE_DURATION, function () {
          currentTarget.hide();
          target
            .stop()
            .css({'opacity': 0, 'display': 'block'})
            .animate({ opacity: 1 }, TAB_ANIMATE_DURATION, function () {
              currentTarget.removeClass(activePanelClassName);
              target.addClass(activePanelClassName);
            });
        });

      item.siblings().removeClass(activeTabClassName);
      item.addClass(activeTabClassName);
    });

    $('.post-toc a').on('click', function (e) {
      e.preventDefault();
      var targetSelector = NexT.utils.escapeSelector(this.getAttribute('href'));
      var offset = $(targetSelector).offset().top;
      hasVelocity ?
        html.velocity('stop').velocity('scroll', {
          offset: offset  + 'px',
          mobileHA: false
        }) :
        $('html, body').stop().animate({
          scrollTop: offset
        }, 500);
    });

    // Expand sidebar on post detail page by default, when post has a toc.
    NexT.motion.middleWares.sidebar = function () {
      var $tocContent = $('.post-toc-content');

      if (CONFIG.sidebar.display === 'post' || CONFIG.sidebar.display === 'always') {
        if ($tocContent.length > 0 && $tocContent.html().trim().length > 0) {
          NexT.utils.displaySidebar();
        }
      }
    };
  });
</script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=0.5.0"></script>



  

  
    
  

  <script type="text/javascript">
    var duoshuoQuery = {short_name:"rainboy"};
    (function() {
      var ds = document.createElement('script');
      ds.type = 'text/javascript';ds.async = true;
      ds.id = 'duoshuo-script';
      ds.src = (document.location.protocol == 'https:' ? 'https:' : 'http:') + '//static.duoshuo.com/embed.js';
      ds.charset = 'UTF-8';
      (document.getElementsByTagName('head')[0]
      || document.getElementsByTagName('body')[0]).appendChild(ds);
    })();
  </script>

  
    
  





  
  
  
  <script type="text/x-mathjax-config">
    MathJax.Hub.Config({
      tex2jax: {
        inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
        processEscapes: true,
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
      }
    });
  </script>

  <script type="text/x-mathjax-config">
    MathJax.Hub.Queue(function() {
      var all = MathJax.Hub.getAllJax(), i;
      for (i=0; i < all.length; i += 1) {
        all[i].SourceElement().parentNode.className += ' has-jax';
      }
    });
  </script>

  
    <script type="text/javascript" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
  


  

  

</body>
</html>
